#include <stdio.h>
#define maxSize 7

typedef struct
{
    /* data */
    char data;   //数据域
    int cur;    //游标
}StaticLinkList;

//将结构体数组中所有分量链接到备用链表中
void createLinkList(StaticLinkList* linkList);
//初始化静态链表
int initLinkLis(StaticLinkList* linkList);
//输出函数
void displayLinkList(StaticLinkList* linkList, int head);
//从备用链表上摘下空闲节点的函数
int mallocLinkList(StaticLinkList* linkList);
//向链表中插入数据，head表示链表的头结点在数组中的位置，index表示插入元素的位置，elem表示要插入的数据
void insertLinkList(StaticLinkList* linkList, int head, int inex, char elem);
//删除链表中含有字符elem的结点
void deleteLinkList(StaticLinkList* linkList, int head, char elem);
//查找存储有字符elem的结点在数组的位置
int searchLinkList(StaticLinkList* linkList, int head, char elem);
//将链表中的字符oldElem改为newElem
void replaceLinkList(StaticLinkList* linkList, int head, char oldElem, char newElem);
//将摘除下来的节点链接到备用链表上
void freeLinkList(StaticLinkList* linkList, int index);

int main(int argc, char* argv[]) {
    //创建静态链表
    StaticLinkList linkList[maxSize];
    //链接备用链表
    createLinkList(linkList);
    //初始化
    int head = initLinkLis(linkList);
    printf("静态链表为：\n");
    displayLinkList(linkList, head);

    printf("在第3的位置上插入结点‘e’:\n");
    insertLinkList(linkList, head, 3,'e');
    displayLinkList(linkList, head);

    printf("删除数据域为‘a’的结点:\n");
    deleteLinkList(linkList, head, 'a');
    displayLinkList(linkList, head);

    printf("查找数据域为‘e’的结点的位置:\n");
    int searchResult = searchLinkList(linkList, head,'e');
    printf("%d\n", searchResult);

    printf("查找数据域为‘d’的结点的位置:\n");
    int searchResult2 = searchLinkList(linkList, head,'d');
    printf("%d\n", searchResult2);

    printf("查找数据域为‘x’的结点的位置:\n");
    int searchResult3 = searchLinkList(linkList, head,'x');
    printf("%d\n", searchResult3);

    printf("将结点数据域为‘e’改为‘h’:\n");
    replaceLinkList(linkList, head, 'e', 'h');
    displayLinkList(linkList, head);

    return 0;

}

//创建备用链表
void createLinkList(StaticLinkList* linkList) {
    //将每个数组分量链接到一起
    for(int i=0; i<maxSize; i++) {
        linkList[i].data = ' ';
        linkList[i].cur = i+1;
    }
    //链表最后一个结点的游标值为0
    linkList[maxSize -1].cur = 0;
}

//初始化静态链表
int initLinkLis(StaticLinkList* linkList){
    //获取备用链表头中的空闲节点，即a[0] 的直接后继节点
    int head = mallocLinkList(linkList);
    //声明一个变量，把它当指针使，指向链表的最后的一个结点，因为链表为空，所以和头结点重合
    int tempHead = head;
    //链表最后一个结点的指针为0，遍历至倒数第二位
    for(int i=1; i<maxSize-2; i++) {
        //从备用链表中拿出空闲的分量
        int j = mallocLinkList(linkList);
        linkList[tempHead].cur = j;
        linkList[j].data = 'a' + i - 1;
        tempHead = j;
    }
    //新的链表最后一个结点的指针设置为0
    linkList[tempHead].cur = 0;

    return head;
}

//提取分配空间
int mallocLinkList(StaticLinkList* linkList) {
    //若备用链表非空，则返回分配的结点下标，否则返回0（当分配最后一个结点时，该结点的游标值为0）
    int i = linkList[0].cur;
    if(linkList[0].cur) {
        //向备用链表头中添加空闲节点，作为 a[0] 新的直接后继节点
        linkList[0].cur = linkList[i].cur;
    }
    return i;
}

//输出函数
void displayLinkList(StaticLinkList* linkList, int head){
    //tempHead准备做遍历使用
    int tempHead = head;
    while(linkList[tempHead].cur) {
        printf("%c,%d \n", linkList[tempHead].data, linkList[tempHead].cur);
        tempHead = linkList[tempHead].cur;
    }
    //链表最后一个结点的游标值为0，单独打印
    printf("%c,%d \n", linkList[tempHead].data, linkList[tempHead].cur);

}

//向链表中插入数据，head表示链表的头结点在数组中的位置，index表示插入元素的位置，elem表示要插入的数据
void insertLinkList(StaticLinkList* linkList, int head, int index, char elem) {
    //tempHead做遍历结构体数组使用
    int tempHead = head;
    //找到要插入位置的上一个结点在数组中的位置
    for(int i=1; i<index; i++) {
        tempHead = linkList[tempHead].cur;
    }
    //获取备用链表头中的空闲节点，即a[0] 的直接后继节点
    int insertIndex = mallocLinkList(linkList);
    linkList[insertIndex].data = elem;
    //新插入结点的游标等于其直接前驱结点的游标
    linkList[insertIndex].cur = linkList[tempHead].cur;
    linkList[tempHead].cur = insertIndex;
}

//删除结点函数，elem 表示被删除结点中数据域存放的数据
void deleteLinkList(StaticLinkList* linkList, int head, char elem) {
    //tempHead做遍历结构体数组使用
    int tempHead = head;
    //找到被删除结点的位置
    while(linkList[tempHead].data != elem) {
        tempHead = linkList[tempHead].cur;
        //当tempHead为0时，表示链表遍历结束，说明链表中没有存储该数据的结点
        if(tempHead == 0) {
            printf("未找到");
            return;
        }
    }
    //运行到此，证明有该结点
    int delIndex = tempHead;
    //tempHead做遍历结构体数组使用
    tempHead = head;
    //找到该结点的上一个结点，做删除操作
    while(linkList[tempHead].cur != delIndex) {
        tempHead = linkList[tempHead].cur;
    }
    //将存有目标元素的节点从数据链表中摘除
    linkList[tempHead].cur = linkList[delIndex].cur;
    //将摘除节点添加到备用链表,回收被摘除节点的空间
    freeLinkList(linkList, delIndex);
}

//将摘除下来的节点链接到备用链表上
void freeLinkList(StaticLinkList* linkList, int index) {
    //查找备用链表头中空闲节点，即 a[0] 的直接后继节点
    int tempHead = linkList[0].cur;
    //原备用链表头中空闲节点链接到待摘除节点
    linkList[index].cur = tempHead;
    //摘除下来的节点链接到备用链表的表头
    linkList[0].cur = index;
}

//查找存储有字符elem的结点在数组的位置
int searchLinkList(StaticLinkList* linkList, int head, char elem) {
    //tempHead做遍历结构体数组使用
    int tempHead = head;
    //当游标值为0时，表示链表结束
    while(linkList[tempHead].data != elem) {
        tempHead = linkList[tempHead].cur;
        //当tempHead为0时，表示链表遍历结束，说明链表中没有存储该数据的结点
        if(tempHead == 0) {
            printf("未找到");
            //返回-1，表示在链表中没有找到该元素
            return -1;
        }
    }
    //运行到此，证明有该结点
    return tempHead;
}

//将链表中的字符oldElem改为newElem
void replaceLinkList(StaticLinkList* linkList, int head, char oldElem, char newElem) {
    //查找oldElem位置
    int searchResult = searchLinkList(linkList, head, oldElem);
    if(searchResult == -1) {
        printf("未找到");
        return; 
    }
    linkList[searchResult].data = newElem;
}